#ifndef STACK_H_
#define STACK_H_
#include <iostream>
#include <cstdlib>
#include "Public.h"

using namespace std;

template <typename ElemType>
class Stack {

public:
	Stack();
	~Stack();

	Status clearStack();

	bool isEmpty() const;
	bool isFull() const;
	int getLength() const;
	ElemType getTop() const;
	ElemType Pop();
	Status Push(ElemType key);
	Status show_stack() const;
	template <typename ElemType>
	friend ostream &operator<<(ostream &output, Stack<ElemType> &stack);

private:
	int m_iStackSize;
	ElemType *m_ptrTop;
	ElemType *m_ptrBase;

};

template <typename ElemType>
Stack<ElemType>::Stack() {
	m_ptrBase = (ElemType *)malloc(sizeof(ElemType)*stack_ini_size);
	if (m_ptrBase == NULL) {
		perror("Memory allocation failed!");
		exit(EXIT_FAILURE);
	}
	m_ptrTop = m_ptrBase;
	m_iStackSize = stack_ini_size;
}

template <typename ElemType>
Stack<ElemType>::~Stack() {
	free(m_ptrBase);
	m_ptrTop = NULL;
	m_ptrBase = NULL;
}

template <typename ElemType>
Status Stack<ElemType>::clearStack() {
	m_ptrTop = m_ptrBase;
	return OK;
}

template <typename ElemType>
bool Stack<ElemType>::isEmpty() const{
	return m_ptrBase == m_ptrTop;
}

template <typename ElemType>
bool Stack<ElemType>::isFull() const{
	return m_ptrTop - m_ptrBase == m_iStackSize;
}

template <typename ElemType>
int Stack<ElemType>::getLength() const{
	return m_ptrTop - m_ptrBase;
}

template <typename ElemType>
ElemType Stack<ElemType>::getTop() const{
	if (isEmpty()) {
		perror("Current stack is empty!!\n");
		return ERROR;
	}
	return *(m_ptrTop - 1);
}

template <typename ElemType>
ElemType Stack<ElemType>::Pop() {
	if (isEmpty()) {
		perror("Current stack is empty!!\n");
		return ERROR;
	}
	return *--m_ptrTop;
}

template <typename ElemType>
Status Stack<ElemType>::Push(ElemType key) {
	if (isFull()) {
		ElemType *p = (ElemType *)realloc(m_ptrBase, sizeof(ElemType)*(stack_ini_size + stack_incre_size));
		if (p == NULL) {
			perror("Failed to reallocate memory!");
			exit(EXIT_FAILURE);
		}
		int len = m_ptrTop - m_ptrBase;
		m_ptrBase = p;
		m_ptrTop = m_ptrBase + len;
		m_iStackSize += stack_incre_size;
	}
	*m_ptrTop = key;
	++m_ptrTop;
	return OK;
}

template <typename ElemType>
Status Stack<ElemType>::show_stack() const{
	ElemType *pointer = m_ptrTop;

	do {
		--pointer;
		cout << *pointer;
	} while (pointer != m_ptrBase);
	cout << endl;
	return OK;
}


template <typename ElemType>
ostream &operator<<(ostream &output, Stack<ElemType> &stack) {
	ElemType *pointer = stack.m_ptrTop;

	do {
		--pointer;
		output << *pointer;
	} while (pointer != stack.m_ptrBase);
	output << endl;
	return output;
}

#endif